1430G - Yet Another DAG Problem - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=402,M=260981;
typedef long long ll;
const ll inf=1e18;
int out[N],in[N],s,t,n,m,x,y,z,w,h[N],cnt=1,gap[M],dep[N],ans[N],c[N];
struct hbs{int x,y,w;}f[N];
struct edge{int to,ne;ll val;}e[M];
int d(int x,int y){return (x-1)*(n+2)+y+1;}
void add(int x,int y,ll w){e[++cnt]={y,h[x],w},h[x]=cnt;}
void link(int x,int y,ll w){add(x,y,w),add(y,x,0);}
queue<int> q;
void bfs(int st){
	memset(dep,0xff,sizeof(dep));
	memset(gap,0,sizeof(gap));
	q.push(st);
	gap[dep[st]=0]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=h[x],y;i;i=e[i].ne){
			y=e[i].to;
			if(dep[y]<0){
				gap[dep[y]=dep[x]+1]++;
				q.push(y);
			}
		}
	}
}
void bfs2(int st){
	memset(dep,0xff,sizeof(dep));
	q.push(st);
	dep[st]=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=h[x],y;i;i=e[i].ne){
			y=e[i].to;
			if(e[i].val&&dep[y]<0){
				dep[y]=dep[x]+1;
				q.push(y);
			}
		}
	}
}
ll dfs(int u,ll inflow){
	if(u==t)return inflow;
	ll outflow=0;
	for(int &i=c[u];i;i=e[i].ne){
		int v=e[i].to;
		if(e[i].val&&dep[v]+1==dep[u]){
			ll res=dfs(v,min(inflow-outflow,e[i].val));
			e[i].val-=res,e[i^1].val+=res,outflow+=res;
			if(inflow==outflow)return outflow;
		}
	}
	if((--gap[dep[u]])==0)dep[s]=2*t;
	dep[u]++,gap[dep[u]]++;
	return outflow;
}
void ISAP(){
	bfs(t);
	while(dep[s]<2*t){
		memcpy(c,h,sizeof(h));
		dfs(s,1e18);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		f[i]={x,y,z};
		out[x]+=z,in[y]+=z;
	}
	s=n*(n+2)+1,t=s+1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=n;++j)link(d(i,j),d(i,j+1),inf);
		link(s,d(i,n+1),inf);
		for(int j=0;j<=n;++j)link(s,d(i,j),out[i]);
		link(d(i,0),t,inf);
		for(int j=1;j<=n+1;++j)link(d(i,j),t,in[i]);
	}
	for(int i=1;i<=m;++i){
		x=f[i].x,y=f[i].y;
		for(int j=1;j<=n+1;++j)link(d(x,j),d(y,j-1),inf);
	}
	ISAP();
	bfs2(s);
	for(int i=1;i<=n;++i){
		for(int j=n+1;j;--j){
			ans[i]=j;
			if(dep[d(i,j)]<0)break;
		}
	}
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);
	return 0;
}